home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1993 / Internet Info CD-ROM (Walnut Creek) (1993).iso / inet / ien / ien-196 < prev    next >
Text File  |  1988-12-01  |  44KB  |  1,344 lines
  1.  
  2. IEN 196 11 September 1981
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.           ISSUES INVOLVING NON-ROUTING GATEWAYS
  18.  
  19.  
  20.  
  21.                     B. Bowman & P. Cook
  22.  
  23.  
  24.         Ford Aerospace & Communications Corporation
  25.  
  26.                  Colorado Springs, Colorado
  27.  
  28.                         (303-471-9110)
  29.  
  30.  
  31.                          IEN # 196
  32.  
  33.  
  34.  
  35.                     September 11, 1981
  36.  
  37.  
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59. IEN 196 11 September 1981
  60.  
  61.  
  62. INTRODUCTION
  63.  
  64. This  note  presents  some  proposed modifications to the gateway
  65. routing  algorithm  and  the  protocol  for  exchanging   routing
  66. information described in IEN #109, "How To Build A Gateway".  The
  67. described algorithm modifications were defined  as  a  result  of
  68. problems  encountered  in  the  implementation  of the gateway to
  69. gateway control protocol specified in IEN #  109.   The  problems
  70. encountered  in implementing the algorithm involve the mechanisms
  71. for  incorporating   non-routing   gateways   in   the   catenet.
  72. Therefore,  this  discussion focuses on modifications designed to
  73. facilitate use of non-routing gateways in  concert  with  routing
  74. gateways in the catenet.
  75.  
  76. As  indicated  above,  the  issues  discussed  resulted  from our
  77. implementation  of  the  IEN  #  109  algorithm.   Some   initial
  78. implementation  questions  concerning interpretation of the rules
  79. for assembling routing updates from non-routing gateways  led  to
  80. our  analysis  of  the  design  of  this  routing strategy.  From
  81. routing strategy design issues, our study progressed to questions
  82. regarding  the  intended/optimal  role of non-routing gateways in
  83. the catenet.
  84.  
  85. As a result, this note presents specific modifications to  IEN  #
  86. 109  necessary  for  successful  implementation and also includes
  87. discussion of the broader issues of the role of  the  non-routing
  88. gateway in the catenet.
  89.  
  90. Finally,  we  propose  a  modification to the routing information
  91. exchanged in the IEN  #  109  algorithm,  which  we  believe  has
  92. significant  advantages in reducing the logical complexity of the
  93. algorithm and traffic between gateways.  Although we have  looked
  94. at  design approaches of other authors in this field, we have not
  95. done an exhaustive search  to  determine  the  "novelty"  of  our
  96. approach.   We would also like to stress that our goal was not to
  97. design a new routing algorithm but simply to implement the IEN  #
  98. 109  algorithm.   In  a  very  real sense, it can be said that we
  99. backed into these routing design issues as a natural  consequence
  100. to our implementation efforts.
  101.  
  102. I. Non-Routing Gateways
  103.  
  104. It  should  be  noted  that  any  solution  must  be  based on an
  105. understanding regarding the  intended  role  of  the  non-routing
  106. gateway  in  the  catenet.   Unambiguous  rules for incorporating
  107. non-routing gateways in the routing scheme can only be  specified
  108. when  the intended role is clearly defined.  An optimal solution,
  109. then, would involve clarification of the role of the  non-routing
  110. gateway   followed  by  revision  of  the  routing  specification
  111. consistent with the defined role.
  112.  
  113.                                 -2-
  114.  
  115.  
  116.  
  117. IEN 196 11 September 1981
  118.  
  119.  
  120. IEN # 109, "How to Build a Gateway", contains a section  (Sect.9,
  121. Page  7)  discussing  the  interface between routing gateways and
  122. non-routing gateways and, in particular, discussing the use of  a
  123. non-routing  gateway  by  a  routing gateway for routing packets.
  124. Two areas of this section  are  problematic  with  respect  to  a
  125. successful  implementation.   These  are, (1) initialization with
  126. respect to the non-routing gateway and  (2)  computation  of  the
  127. minimum distance vector.
  128.  
  129. A. Initialization
  130.  
  131. IEN  # 109 gives the following instructions for initializing with
  132. respect to a non-routing neighbor gateway.
  133.  
  134.  * "For each non-routing neighbor gateway of gateway G1,  compute
  135. the  routing  update  that  would be sent to G1 assuming that all
  136. gateways and network connections are operational.  These  routing
  137. updates are assembled in G1."
  138.  
  139. This rule can be interpreted in one of two ways.  The first is to
  140. assemble the non-routing gateway's routing update showing  actual
  141. distances to each network from the non-routing gateway.  Figure 1
  142. shows an example of this interpretation.
  143.  
  144. In this example, Gateway (B) is a non-routing gateway and Gateway
  145. (A)  is  a  routing  gateway.   Initially,  G(A) assembles G(B)'s
  146. update as actual distances from G(B) to the 3 networks.  Based on
  147. this initialization, G(A) assumes that it is a distance of 1 from
  148. Net.#1 because the non-routing gateway provides the only path  to
  149. Net.#1.   G(A)  also assumes that it is directly (0) connected to
  150. Nets.#2 and #3.  G(A) builds its initial minimum distance  vector
  151. reflecting these distances.
  152.  
  153. Assume,  then, that G(A)'s link to Net.#3 goes down at some time.
  154. When this happens, G(A) recomputes it's minimum distance  vector.
  155. Since  G(A)  is  no  longer connected to Net.#3, there is no path
  156. available unless the non-routing gateway's path is used.   G(B)'s
  157. update  indicates  a  distance  of  1 to Net.#3.  Therefore, G(A)
  158. assumes a path to Net.#3 of distance 2 through G(B).  Of  course,
  159. there  is  no path to Net.#3 but G(B) does not accept or transmit
  160. routing tables so any packets addressed to  Net.#3  will  shuttle
  161. indefinitely  (until the IP4 time to live field is decremented to
  162. zero) from G(A) to G(B) to  G(A),  etc.   When  this  example  is
  163. extended  to  larger catenets, the shuttling problem persists and
  164. simply  involves  higher  distance  shuttles.   Therefore,   this
  165. interpretation of the initialization instructions is unworkable.
  166.  
  167.  
  168.                                -3- 
  169.  
  170.  
  171.  
  172. IEN 196 11 September 1981
  173.  
  174.  
  175.     
  176.  
  177.      FIGURE 1:   INITIALIZATION OF NON-ROUTING GATEWAY UPDATE
  178.                  "ACTUAL DISTANCE" METHOD
  179.  
  180.  
  181. CATENET CONFIGURATION
  182.  
  183.  
  184.  
  185.  __________              __________              __________
  186. |          |            |          |            |          |
  187. |  NET #1  |----G(B)----|  NET #2  |----G(A)----|  NET #3  |
  188. |__________|            |__________|            |__________|
  189.  
  190.  
  191. where
  192.     G(A) = Gateway A:  Routing Gateway
  193.     G(B) = Gateway B:  Non-Routing Gateway
  194.  
  195.  
  196. G(A) DISTANCE MATRIX AFTER INITIALIZATION
  197.  
  198.                           NETWORKS
  199.    GATEWAYS              1    2    3
  200.  
  201.  
  202.       A                  1    0    0
  203.       B                  0    0    1
  204.  
  205.  
  206.  
  207. G(A) DISTANCE MATRIX (ASSUMING LOSS OF CONNECTIVITY TO NET.#3)
  208.  
  209.                           NETWORKS
  210.    GATEWAYS              1    2    3    
  211.  
  212.  
  213.       A                  1    0    2
  214.       B                  0    0    1
  215.  
  216.  
  217.     
  218.  
  219.  
  220.                                -4-
  221.  
  222.  
  223.  
  224. IEN 196                                         11 September 1981
  225.  
  226.  
  227. The  other  possible interpretation of the IEN # 109 instructions
  228. is to assemble the non-routing gateway's  update  showing  actual
  229. distances  to each network from the non-routing gateway only when
  230. the non-routing gateway is as close to or closer to  the  network
  231. than   the   gateway   assembling   the   routing  update.   This
  232. interpretation  incorporates  a  rule  from  Section  7,  page  7
  233. regarding  computation  of  routing  updates.   Figure 2 shows an
  234. example of this interpretation.
  235.  
  236. In this example, Gateway (B is a non-routing gateway and Gateways
  237. A and C are routing gateways.  The example is presented from  the
  238. perspective  of  Gateway  A.   Gateway  B's update is initialized
  239. showing 0 distance to Nets.#1 and #2.  A distance of 1  is  shown
  240. to  Net.#3  because Gateway B is as close to Net.#3 as is Gateway
  241. A.  An infinite distance is shown to Net.#4 because Gateway A  is
  242. closer  to Net.#4 than Gateway B.  The example shows receipt of a
  243. routing update from Gateway C which shows Gateway  C's  distances
  244. calculated  according  to  the rules for preparation of a routing
  245. update.
  246.  
  247. Gateway  A  calculates  its minimym distance vector as 0 distance
  248. from Nets.#2 and #4 because they are directly connected, distance
  249. 1  from Net.#1 because of the path through Gateway B and distance
  250. 1 from Net.#3 because of the path through Gateway C.
  251.  
  252. Assuming  that Gateway C loses connectivity to Network #3 at some
  253. time, Gateway C would send Gateway A a new routing update showing
  254. infinite   distance   to   Network  #3.   Gateway  A  would  then
  255. recalculate its minimum distance vector.  G(A) would assume  that
  256. the only path to Net.#3 is through the non-routing gateway (G(B))
  257. and that this is a path of distance 2.  This occurs because  G(B)
  258. neither accepts nor transmits routing updates so it is unaware of
  259. the connectivity loss and G(A) is assembled with  G(B)'s  routing
  260. update  so  there is no provision for changes to this information
  261. in G(A).  The situation is complicated by  the  fact  that  G(A),
  262. upon  recalculation of its minimum distance vector, will transmit
  263. a routing update to G(C) showing the distance of 2 from  G(A)  to
  264. Network  #3.   G(C)  will recompute its distance vector to show a
  265. path of distance 3 from  G(C)  to  Network  #3.   Since  no  path
  266. actually exists and all 3 Gateways believe a path exists, packets
  267. addressed to Net.#3 will shuttle indefinitely (until the IP4 time
  268. to live field is decremented to zero).
  269.  
  270. Thus it seems that Thus it seems that both interpretations of the
  271. IEN  #  109  instruction for assembling the non-routing gateway's
  272. update present serious problems.
  273.  
  274.  
  275.                                -5-
  276.  
  277.  
  278.  
  279. IEN 196                                         11 September 1981
  280.  
  281.  
  282.     
  283.  
  284.      FIGURE 2:   INITIALIZATION OF NON-ROUTING GATEWAY UPDATE
  285.                  "TAILORED UPDATE" METHOD
  286.  
  287.  
  288. CATENET CONFIGURATION
  289.  
  290.  
  291.                                                  __________
  292.  __________              __________             |          |
  293. |          |            |          |----G(A)----|  NET #4  |
  294. |  NET #1  |----G(B)----|  NET #2  |            |__________|
  295. |          |            |          |             __________
  296. |          |            |          |            |          |
  297. |__________|            |__________|----G(C)----|  NET #3  |
  298.                                                 |__________|
  299.  
  300.  
  301.  
  302. where
  303.    G(A) = Gateway A:  Routing Gateway
  304.    G(B) = Gateway B:  Non-Routing Gateway
  305.    G(C) = Gateway C:  Routing Gateway
  306.  
  307.  
  308. G(A) DISTANCE MATRIX AFTER INITIALIZATION
  309.  
  310.                           NETWORKS
  311.    GATEWAYS              1    2    3    4
  312.  
  313.  
  314.       A                  1    0    1    0
  315.       B                  0    0    1   INF
  316.       C                  1    0    0   INF
  317.  
  318.  
  319.  
  320. G(A) DISTANCE MATRIX (ASSUMING LOSS OF CONNECTIVITY TO NET.#3)
  321.  
  322.                           NETWORKS
  323.    GATEWAYS              1    2    3    4
  324.  
  325.  
  326.       A                  1    0    2    0
  327.       B                  0    0    1   INF
  328.       C                  1    0   INF  INF
  329.  
  330.     
  331.  
  332.  
  333.                                -6-
  334.  
  335.  
  336.  
  337. IEN 196                                         11 September 1981
  338.  
  339.  
  340. B.  Computation of the Minimum Distance Vector
  341.  
  342. IEN # 109 goes on  to  provide  the  following  instructions  for
  343. calculating the minimum distance vector when non-routing gateways
  344. are included.
  345.  
  346.  *  "The  gateway,  G(A),  first  computes  its minimum distance
  347.     vector using only the routing updates  from  neighbors  that
  348.     participate  in  routing.   If  the  minimum distance to any
  349.     network is infinity, i.e., the network  is  unreachable  via
  350.     any  of  the  routing gateways, then the minimum distance to
  351.     that  network  is  re-computed  using  the  routing   update
  352.     compiled for the non-routing neighbor gateway."
  353.  
  354. This rule appears inefficient if we look at the example shown  in
  355. Figure  3.   In  this example, Gateway B is a non-routing gateway
  356. and Gateways A and  C  are  routing  gateways.   The  example  is
  357. presented  from the perspective of Gateway A and the focus of the
  358. example is on the distance to Network #1.
  359.  
  360. G(A)  is  assembled  with  the  update  of  G(B) (the non-routing
  361. gateway) and G(B) shows a distance of 0 from Net.#1 since  it  is
  362. directly  connected.  In our example, G(A) has received an update
  363. from G(C).  G(C) shows a distance of 1 to  Net.#1  based  on  its
  364. path through G(B).  According to the rule, G(A) has to prefer the
  365. route through G(C) since G(C) is a routing neighbor and  G(B)  is
  366. non-routing.   Therefore,  G(A)  assumes  a path of distance 2 to
  367. Net.#1 and G(A) will route  to  G(C)  any  packets  addressed  to
  368. Net.#1.   On receipt of the packet addressed to Net.#1, G(C) will
  369. route the packet to G(B) where it will be delivered to Net.#1.
  370.  
  371. This  solution  is  not  unworkable  but  it does cause delay and
  372. inefficiency by forcing an additonal transfer with respect to the
  373. optimal  path.  In a geographically dispersed network, this delay
  374. and additional network traffic could become significant.
  375.  
  376.  
  377.                                -7-
  378.  
  379.  
  380.  
  381. IEN 196                                         11 September 1981
  382.  
  383.     
  384.  
  385.      FIGURE 3:   COMPUTATION OF THE MINIMUM DISTANCE VECTOR
  386.  
  387.  
  388.  
  389. CATENET CONFIGURATION
  390.  
  391.  
  392.                                                  __________
  393.  __________              __________             |          |
  394. |          |            |          |----G(A)----|  NET #4  |
  395. |  NET #1  |----G(B)----|  NET #2  |            |__________|
  396. |          |            |          |             __________
  397. |          |            |          |            |          |
  398. |__________|            |__________|----G(C)----|  NET #3  |
  399.                                                 |__________|
  400.  
  401.  
  402.  
  403. where
  404.    G(A) = Gateway A:  Routing Gateway
  405.    G(B) = Gateway B:  Non-Routing Gateway
  406.    G(C) = Gateway C:  Routing Gateway
  407.  
  408.  
  409. G(A) DISTANCE MATRIX 
  410.  
  411.                           NETWORKS
  412.    GATEWAYS              1    2    3    4
  413.  
  414.  
  415.       A                  2    0    1    0
  416.       B                  0    0    1   INF
  417.       C                  1    0    0    1
  418.  
  419.     
  420.  
  421.  
  422.                                -8-
  423.  
  424.  
  425.  
  426. IEN 196                                         11 September 1981
  427.  
  428.  
  429. C.  Proposed Solution to Non-Routing Gateway Problems
  430.  
  431. Role Clarification
  432.  
  433. As indicated above, a solution to the problems  in  incorporation
  434. of non-routing gateways must address clarification of the role of
  435. the non-routing gateway in the catenet.  Three possible roles for
  436. the non-routing gateway have been identified and are discussed in
  437. this section.  In  general,  we  see  potential  for  non-routing
  438. gateways   to  be  used  to  provide  1)  the  "only"  route,  2)
  439. "redundant"  routes  or  3)  "parallel"  routes.   Use   of   the
  440. non-routing  gateway to provide "redundant" and "parallel" routes
  441. is discussed in Section D.
  442.  
  443. Figure  4  illustrates  use of the non-routing gateway to provide
  444. the "only" route.  This  role  basically  restricts  the  use  of
  445. non-routing  gateways  to  allow  (i.e.,  recognize)  them in the
  446. catenet only when the non-routing  gateway  provides  the  "only"
  447. connection to a network or network branches.
  448.  
  449. Although other possible roles will be discussed , this particular
  450. role  definition  is  the  one  we  recommend.  Using non-routing
  451. gateways where they provide the "only" possible route  seems  the
  452. most  logical  use  of  these gateways and also lends itself most
  453. easily  to  unambiguous  rule  definition.   The  mechanisms  for
  454. incorporating  non-routing  gateways  consistent  with the "only"
  455. route role are described in the following paragraphs.
  456.  
  457.  
  458.  
  459.  
  460.  
  461.  
  462.  
  463.  
  464.  
  465.  
  466.  
  467.  
  468.  
  469.  
  470.                                -9-
  471.  
  472.  
  473.  
  474. IEN 196                                         11 September 1981
  475.  
  476.  
  477.     
  478.  
  479.      FIGURE 4:   NON-ROUTING GATEWAY AS "ONLY" ROUTE
  480.  
  481.  
  482. CATENET CONFIGURATION
  483.  
  484.  
  485.  
  486.  __________              __________
  487. |          |            |          |
  488. |  NET #1  |----G(R)----|  NET #3  |
  489. |__________|            |__________|
  490.       |                       |
  491.       |                       |
  492.     G(R)                      |
  493.       |                       |
  494.       |                       |
  495.  __________                   |
  496. |          |                  |
  497. |  NET #2  |----G(R)----------|
  498. |__________|
  499.       |
  500.       |
  501.     G(NR)
  502.       |
  503.       |
  504.  __________
  505. |          |
  506. |  NET #4  |
  507. |__________|
  508.       |
  509.       |
  510.    etc. (network branch)
  511.  
  512.  
  513.  
  514.    G(R) = Routing Gateway
  515.    G(NR) = Non-Routing Gateway
  516.  
  517.  
  518. NOTE:   In this configuration, the non-routing gateway provides
  519.         the only connection to Network #4.
  520.  
  521.  
  522.                               -10-
  523.     
  524.  
  525.  
  526.  
  527. IEN 196                                         11 September 1981
  528.  
  529.  
  530. Rules for "Only" Route Role
  531.  
  532. It appears that the initialization and route computation problems
  533. associated with non-routing neighbor  gateways  described  above,
  534. could  be  solved  by a few rule changes.  The proposed new rules
  535. are as follows:
  536.  
  537.  *  IEN # 109 Rule:
  538.  
  539.     For   each  non-routing  neighbor  gateway  of  gatewayG(A),
  540.     compute the routing  update  that  would  be  sent  to  G(A)
  541.     assuming  that  all  gateways  and  network  connections are
  542.     operational.  These routing updates are assembled in G(A).
  543.  
  544.     New Rule:
  545.  
  546.     F or each non-routing  neighbor  gateway  of  gateway  G(A),
  547.     compute  the  routing  update  that  would  be  sent to G(A)
  548.     assuming that  all  gateways  and  network  connections  are
  549.     operational.   In  computing  these  routing  updates,  show
  550.     actual  (non-infinite)  distances  to  networks  which   are
  551.     reachable  only  through  the non-routing gateway.  Networks
  552.     which  are  reachable  by  a  routing   gateway   shall   be
  553.     initialized  with  distance  equal  infinity.  These routing
  554.     updates are assembled in G(A).
  555.  
  556.     IEN # 109 Rule:
  557.  
  558.     T he gateway, G(A),  first  computes  its  minimum  distance
  559.     vector  using  only  the routing updates from neighbors that
  560.     participate in routing.  If  the  minimum  distance  to  any
  561.     network  is  infinity, (i.e., the network is unreachable via
  562.     any of the routing gateways), then the minimum  distance  to
  563.     that   network  is  re-computed  using  the  routing  update
  564.     compiled for the non-routing neighbor gateway.
  565.  
  566.     New Rule:
  567.  
  568.     The gateway,  G(A),  first  computes  its  minimum  distance
  569.     vector using all the routing updates (including updates from
  570.     both routing and non-routing gateways).
  571.  
  572. These  proposed  rule  changes, taken together, cause non-routing
  573. gateways to be used only when they provide the  only  path  to  a
  574. network  or  string  of networks.  These rules also eliminate the
  575. possibility of selecting any other path (i.e., through a  routing
  576. gateway)  when  a  non-routing  gateway  provides  the only path.
  577. Thus, non-routing gateways are used for packet routing if and
  578. only if they provide the only route to a destination.
  579.  
  580.  
  581.  
  582.                               -11-
  583.  
  584.  
  585.  
  586. IEN 196                                         11 September 1981
  587.  
  588.  
  589. Figure 5 shows how the new rules solve the problems identified in
  590. Examples  1,  2,  and  3.   In  this  example,  Gateway  B  is  a
  591. non-routing Gateway and Gateways A and C  are  routing  gateways.
  592. The  example is presented from the perspective of Gateway A.  The
  593. G(A) Distance Matrix after initialization shows that the  problem
  594. depicted in Figure 3 (computation of the minimum distance vector)
  595. is resolved through application of  the  new  rules.   Since  the
  596. minimum  distance  vector  is  calculated  based  equally  on the
  597. routing and non-routing gateway updates, the shortest  path  (and
  598. only  path)  to  Network  #1 is selected by both routing gateways
  599. (G(A) and G(C)).
  600.  
  601. The  G(A)  Distance Matrix resulting from loss of connectivity to
  602. Net.#4  shows   that   the   problem   depicted   in   Figure   1
  603. (Initialization   of  non-routing  gateway  update)  is  resolved
  604. through use of the new rules.  Since  the  assembled  non-routing
  605. gateway  update  no  longer  shows paths to networks reachable by
  606. routing gateways, G(A) is able to determine that  Net.#4  is  now
  607. unreachable  and  does  not  attempt  to  route traffic to Net.#4
  608. through Gateway (B).
  609.  
  610. The  G(A)  Distance Matrix resulting from loss of connectivity to
  611. Net.#3  shows   that   the   problem   depicted   in   Figure   2
  612. (Initialization  of  non-routing Gateway update) is also resolved
  613. through application of the new rules.  This problem  is  resolved
  614. because  the  assembled non-routing gateway update no longer show
  615. paths to networks reachable  by  routing  gateways.   Thus,  when
  616. Net.#3 is declared unreachable by Gateway C, G(A) determines that
  617. Net.#3 is unreachable by all gateways.
  618.  
  619.  
  620.  
  621.  
  622.  
  623.  
  624.  
  625.  
  626.  
  627.  
  628.  
  629.  
  630.  
  631.  
  632.  
  633.  
  634.                               -12-
  635.  
  636.  
  637.  
  638. IEN 196                                         11 September 1981
  639.     
  640.      FIGURE 5:   PROPOSED SOLUTION
  641.  
  642. CATENET CONFIGURATION
  643.                                                  __________
  644.  __________              __________             |          |
  645. |          |            |          |----G(A)----|  NET #4  |
  646. |  NET #1  |----G(B)----|  NET #2  |            |__________|
  647. |          |            |          |             __________
  648. |          |            |          |            |          |
  649. |__________|            |__________|----G(C)----|  NET #3  |
  650.                                                 |__________|
  651.  
  652. where
  653.  
  654.    G(A) = Gateway A:  Routing Gateway
  655.    G(B) = Gateway B:  Non-Routing Gateway
  656.    G(C) = Gateway C:  Routing Gateway
  657.  
  658. G(A) DISTANCE MATRIX AFTER INITIALIZATION
  659.  
  660.                           NETWORKS
  661.    GATEWAYS              1    2    3    4
  662.  
  663.       A                  1    0    1    0
  664.       B                  0   INF  INF  INF
  665.       C                  1    0    0   INF
  666.  
  667.  
  668. G(A) DISTANCE MATRIX (ASSUMING LOSS OF CONNECTIVITY TO NET.#4)
  669.  
  670.                           NETWORKS
  671.    GATEWAYS              1    2    3    4
  672.  
  673.       A                  1    0    1   INF
  674.       B                  0   INF  INF  INF
  675.       C                  1    0    0   INF
  676.  
  677.  
  678. G(A) DISTANCE MATRIX (ASSUMING LOSS OF CONNECTIVITY TO NET.#3)
  679.  
  680.                           NETWORKS
  681.    GATEWAYS              1    2    3    4
  682.  
  683.       A                  1    0   INF   0
  684.       B                  0   INF  INF  INF
  685.       C                  1    0   INF  INF
  686.  
  687.  
  688.                               -13-
  689.     
  690.  
  691.  
  692.  
  693. IEN 196                                         11 September 1981
  694.  
  695.  
  696. D.  Other Possible Approaches
  697.  
  698. Redundant Role
  699.  
  700. Restricting the use of non-routing gateways  in  the  catenet  to
  701. locations  where  they  provide  the  only  configured  path  and
  702. adoption of the corresponding rule  changes  is  our  recommended
  703. solution  to  the  implementation  problems we've identified.  In
  704. reviewing IEN # 109 and it's predecessor IEN #  30,  we  find  it
  705. difficult  to  determine  the  intended  role  of the non-routing
  706. gateways.
  707.  
  708. Both  papers indicate that non-routing gateways are to be used to
  709. forward traffic only when  they  provide  the  only  route  to  a
  710. network.   This  seems to indicate that the initial intent was to
  711. use non-routing gateways in the role defined above (i.e.   "only"
  712. route  role).   On the other hand, it's possible that the authors
  713. actually intended to use the non-routing gateways to provide  the
  714. only  configured  path  and  to provide backup routes to networks
  715. connected  by  routing  gateways.   This  role  for   non-routing
  716. gateways  is what we have called the "redundant " role.  Figure 6
  717. illustrates this use  of  non-routing  gateways.   This  role  is
  718. basically an addition to the "only" route role.
  719.  
  720. Here the non-routing gateway can also be configured  in  parallel
  721. with  a  routing gateway but the non-routing path is only used if
  722. connectivity through the routing  gateway  is  lost.   Thus,  the
  723. non-routing  gateway is used as a backup for the routing gateway.
  724. As  long  as  the  routing  gateway  and  its   connections   are
  725. functional,  the  non-routing  gateway is not used to forward any
  726. traffic.
  727.  
  728.  
  729.  
  730.  
  731.  
  732.  
  733.  
  734.  
  735.  
  736.  
  737.  
  738.  
  739.  
  740.  
  741. 749/
  742.  
  743.                               -14-
  744.  
  745.  
  746.  
  747. IEN 196                                         11 September 1981
  748.  
  749.  
  750.     
  751.  
  752.      FIGURE 6:   NON-ROUTING GATEWAY AS "REDUNDANT" ROUTE
  753.  
  754.  
  755.  
  756. CATENET CONFIGURATION
  757.  
  758.  
  759.  
  760.  __________              __________
  761. |          |----G(NR)---|          |
  762. |  NET #1  |            |  NET #2  |
  763. |__________|----G(R)----|__________|
  764.       |                       |
  765.       |                       |
  766.     G(R)                    G(R)
  767.       |                       |
  768.       |                       |
  769.  __________________________________
  770. |                                  |
  771. |           NET #3                 |
  772. |__________________________________|
  773.  
  774.  
  775. WHERE
  776.    G(R) = Routing Gateway
  777.    G(NR) = Non-Routing Gateway
  778.  
  779.     
  780.  
  781.  
  782.  
  783.  
  784.  
  785.  
  786.                               -15-
  787.  
  788.  
  789.  
  790. IEN 196                                         11 September 1981
  791.  
  792.  
  793.  
  794. It seems that this second role interpretation  is  implementable.
  795. Basically, the corresponding rules would be:
  796.  
  797.  1)  Assemble routing update showing direct network  connections
  798.      and  actual  distances  to  networks  reachable only by the
  799.      non-routing gateway.
  800.  
  801.  2)  Calculate minimum distance vector using non-routing gateway
  802.      paths only when they provide the only route.
  803.  
  804. Implementing   this   role  concept,  then,  involves  the  added
  805. complexity of the two stage minimum distance  vector  calculation
  806. (with  bias toward routing gateway paths).  While this may be the
  807. role anticipated by the authors of IEN # 109 and #  30,  we  feel
  808. the  backup  role  is  of  little  added value for the additional
  809. complexity involved.  It seems unlikely to us that networks would
  810. buy  a  processor  which was to be idle the majority of the time.
  811. Instead, if need existed for a backup, it seems a routing gateway
  812. would  be a better choice and cost efficient as it could increase
  813. bandwidth as well as providing redundancy.
  814.  
  815. Parallel Role
  816.  
  817. At the other end of the spectrum, it is possible that some  group
  818. might wish to use non-routing gateways in any configuration where
  819. routing gateways can be used.  In this role, which  we  call  the
  820. "parallel"   role,  non-routing  gateways  are  used  to  provide
  821. additional  (parallel)  paths  and  thus   effectively   increase
  822. bandwidth.   This role differs from the "redundant" route role in
  823. that non-routing gateways are used to forward traffic  even  when
  824. they  do  not  provide  the only path.  It is this facility which
  825. allows the effective increase in real-time bandwidth.
  826.  
  827. Whether  this intended role is implementable is an open question.
  828. Obviously, it would  be  more  complex  to  implement  and  would
  829. basically require a redefinition of some of the ground rules.  We
  830. rejected this possible role application because it  significantly
  831. reduces  catenet  reliability  and seems to defeat the whole idea
  832. behind the routing algorithm function.  If  non-routing  gateways
  833. are  used  routinely  to forward traffic in parallel with routing
  834. gateways, connectivity  changes  occuring  with  the  non-routing
  835. gateways  are  unreported  and therefore the non-routing gateways
  836. could easily become traffic sinks.
  837.  
  838.  
  839.  
  840.  
  841.  
  842.  
  843.                               -16-
  844.  
  845.  
  846.  
  847. IEN 196                                         11 September 1981
  848.  
  849. We  felt that the only possibility for using non-routing gateways
  850. to increase bandwidth would be to implement the role outside  the
  851. gateway-gateway   control   protocol.   This  function  could  be
  852. implemented as a host function where there was  an  understanding
  853. between hosts on two networks that traffic would be split on some
  854. basis  between  routing  and  non-routing  gateways.   Thus,  the
  855. decision  to  sacrifice catenet reliability in favor of increased
  856. traffic flow would  be  made  by  the  parties  involved  without
  857. involving    any    gateway   control   function   awareness   or
  858. participation.
  859.  
  860. II.  Routing Update Calculations
  861.  
  862. In the process of designing the gateway routing software IAW  IEN
  863. # 109, we determined that a subset of the routing algorithm rules
  864. dictated a logically  cumbersome  implementation.   These  rules,
  865. from IEN # 109 are as follows:
  866.  
  867.  A.  "The gateway  reports  its  distance  to  a  network  to  a
  868.      neighbor only if it is as close or closer to a network than
  869.      its neighbor."  (p.7)
  870.  
  871.  B.  "The  gateway  maintains  a copy of the most recent routing
  872.      updates that it sent to each of its neighbors.  The gateway
  873.      computes  the  new  routing  updates to send to each of its
  874.      neighbors.  If any of these routing updates  are  different
  875.      than  the  preceding  updates,  then  the gateway sends new
  876.      routing updates to its neighbors."  (p.7)
  877.  
  878. Rule  A  calls  for "tailoring" routing updates for each neighbor
  879. such that the transmitting gateway reports its distance  relative
  880. to  the  connectivity  of  each  recipient gateway.  Thus, when a
  881. gateway calculates its routing update, it  first  calculates  its
  882. minimum distance vector and then compares that vector to the last
  883. routing update from each  neighbor.   From  this  comparison,  it
  884. creates  the  "tailored"  routing  update for each neighbor which
  885. reflects not only the  transmitting  gateway's  connectivity  but
  886. also  the  connectivity of each neighbor.  The comparison process
  887. is performed as follows:
  888.  
  889.  
  890.  
  891.  
  892.  
  893.  
  894.  
  895.                               -17-
  896.  
  897.  
  898.  
  899. IEN 196                                         11 September 1981
  900.  
  901.  
  902.         DO (For each neighbor)
  903.  
  904.            DO (For each network)
  905.  
  906.               IF (Transmitting gateway is as close or closer to
  907.  
  908.                  the network)
  909.  
  910.                    Report actual distance
  911.  
  912.               ELSE (Report infinity distance)
  913.  
  914.            ENDDO
  915.  
  916.         ENDDO
  917.  
  918. Rule  B requires that, having performed the calculations based on
  919. Rule A resulting in routing  updates  for  each  neighbor,  these
  920. updates  be  compared  to the updates last sent to each neighbor.
  921. If any of the updates are different from those last sent, all the
  922. updates are transmitted.  If there are no changes to any neighbor
  923. since the last transmittal, no updates are sent.   Implementation
  924. of  this  rule  requires  that copies of the last updates sent be
  925. maintained at the gateway.
  926.  
  927. The  basis for these rules, particularly Rule A, is prevention of
  928. shuttling which could occur if only one path existed to a network
  929. and  that  network became disconnected.  If gateways were allowed
  930. to  report  actual  distances  rather  than  infinity,  then  two
  931. gateways  could,  because of their dependent or relative distance
  932. relationship, begin step increments of  their  distances  to  the
  933. disconnected  network  eventually  approaching  infinity and thus
  934. shuttle packets until the IP4 time to live field  is  decremented
  935. to zero.
  936.  
  937. This shuttling problem is,  in  fact,  a  natural  outcome  of  a
  938. routing   scheme   which   involves   the  exchange  of  distance
  939. information only.   Thus,  the  problem  can  be  solved  by  the
  940. addition  of special rules such as Rule #1 above or can be solved
  941. by  going  to  a  routing  scheme  which  exchanges  connectivity
  942. information (distance and path).
  943.  
  944.  
  945.  
  946.  
  947.  
  948.  
  949.  
  950.  
  951.                               -18-
  952.  
  953.  
  954.  
  955. IEN 196                                         11 September 1981
  956.  
  957.  
  958. After  studying  the  current  solution  of  exchanging  relative
  959. distance  vectors,  it  seems  that  going  to a routing scheme
  960. involving exchange of both connectivity information and  distance
  961. provides  a  simpler  and  more  efficient  solution.   The added
  962. information  exchange  proposed  is  more  than  offset  by   the
  963. computational  simplicity  and  the  reduction  in routing update
  964. traffic afforded.
  965.  
  966. The  routing  scheme  proposed  provides for including in routing
  967. updates both the  actual  distance  vector  (as  opposed  to  the
  968. current tailored relative distance vector) and the routing table.
  969.  
  970. Figure 7 is a configuration used as the basis for illustration of
  971. the  updates.   To see how these routing updates are constructed,
  972. examine the update from G3 in Figure 8 (Step 3).  G3 is  directly
  973. connected to Nets.#2 and #26, so G3 shows a distance of 0 to each
  974. with G3 as the "next" gateway address for routing.  G3 is 1  away
  975. from Net.#1 and this path to Net.#1 is through G2.  Similarly, G3
  976. is 1 away from Nets.#3 and #27 and these paths are through G5 and
  977. G6 respectiviely.  G3 is also a distance of 1 from Net.#10.
  978.  
  979.  
  980.  
  981.  
  982.  
  983.  
  984.  
  985.  
  986.  
  987.  
  988.  
  989.  
  990.  
  991.  
  992.  
  993.  
  994.  
  995.  
  996.  
  997.  
  998.  
  999.  
  1000.  
  1001.  
  1002.  
  1003.  
  1004.                               -19-
  1005.  
  1006.  
  1007.  
  1008. IEN 196                                         11 September 1981
  1009.  
  1010.  
  1011.     
  1012.  
  1013.      FIGURE 7:   CATENET CONFIGURATION
  1014.  
  1015.  
  1016.  
  1017.  __________              __________
  1018. |          |            |          |
  1019. |  NET #1  |            |  NET #4  |
  1020. |__________|            |__________|
  1021.       |                      |
  1022.       |                      |
  1023.      G2                     G4
  1024.       |                      |
  1025.       |                      |
  1026.  __________             __________
  1027. |          |           |          |
  1028. |  NET #26 |-----G1----|  NET #10 |
  1029. |__________|----       |__________|
  1030.       |        |             |
  1031.       |        |             |
  1032.      G3        |------------G5
  1033.       |                      |
  1034.       |                      |
  1035.  __________             __________
  1036. |          |           |          |
  1037. |  NET #2  |           |  NET #3  |
  1038. |__________|           |__________|
  1039.       |
  1040.       |
  1041.      G6
  1042.       |
  1043.       |
  1044.  __________
  1045. |          |
  1046. |  NET #27 |
  1047. |__________|
  1048.  
  1049.  
  1050.  
  1051. NOTE:  Gateways G1 - G6 are all routing gateways.
  1052.  
  1053.     
  1054.  
  1055.  
  1056.  
  1057.  
  1058.                               -20-
  1059.  
  1060.  
  1061.  
  1062. IEN 196                                         11 September 1981
  1063.  
  1064.  
  1065.  
  1066.     
  1067.      FIGURE 8:   ROUTING UPDATES BASED ON NEW ROUTING METHOD
  1068.                  (SEE FIGURE 7 FOR CONFIGURATION)
  1069.  
  1070.  
  1071.           NETWORK DISTANCES/"NEXT" NEIGHBOR ADDRESS(ES)
  1072.  
  1073.  
  1074.  
  1075. STEP   SOURCE   DEST.           1    2    3    4    10    26    27
  1076.  
  1077.  
  1078.  1.     G1      ALL  Distance  INF  INF  INF  INF    0     0    INF
  1079.                       "Next"                        G1    G1
  1080.  
  1081.  2.     G2      ALL  Distance   0    1    1    2     1     0     2
  1082.                       "Next"   G2   G3   G5   G1    G1    G2    G3
  1083.  
  1084.  3.     G2      ALL  Distance   1    0    1    2     1     0     1
  1085.                       "Next"   G2   G3   G5   G1    G1    G3    G6
  1086.                                               G5    G5
  1087.  
  1088.  4.     G4      ALL  Distance   2    2    1    0     0     1     3
  1089.                       "Next"   G1   G1   G5   G4    G4    G1    G1
  1090.                                G5   G5                    G5    G5
  1091.  
  1092.  5.   G5(10)    ALL  Distance   1    1    0    1     0     0     2
  1093.                       "Next"   G2   G3   G5   G4    G5    G5    G3
  1094.  
  1095.  6.   G5(26)    ALL  Distance   1    1    0    1     0     0     2
  1096.                       "Next"   G2   G3   G5   G4    G5    G5    G3
  1097.  
  1098.  7.     G1      ALL  Distance   1    1    1    1     0     0     2
  1099.                       "Next"   G2   G3   G5   G4    G1    G1    G3
  1100.  
  1101.             Assume loss of connectivity by G2 to Net.#1
  1102.  
  1103.  8.     G2      ALL  Distance  INF   1    1    2     1     0     2
  1104.                       "Next"        G3   G5   G5    G5    G2    G3
  1105.                                               G1    G1
  1106.  
  1107.  9.     G1      ALL  Distance  INF   1    1    1     0     0     2
  1108.                       "Next"        G3   G5   G4    G1    G1    G3
  1109.  
  1110.  
  1111. NOTE:   G5(10) is gateway 5 on network 10.  A gateway which is a
  1112.         neighbor on two networks is treated as two gateways.  Thus
  1113.         G5 is identified as G5(10) and G5(26) by Gateway 1.
  1114.  
  1115.     
  1116.                               -21-
  1117.  
  1118.  
  1119.  
  1120. IEN 196                                         11 September 1981
  1121.  
  1122.  
  1123.     
  1124.  
  1125.      FIGURE 9:   ROUTING UPDATES BASED ON IEN # 109 METHOD
  1126.                  (SEE FIGURE 7 FOR CONFIGURATION)
  1127.  
  1128.  
  1129.  
  1130.  
  1131.                          NETWORK DISTANCES
  1132.  
  1133.  
  1134. SOURCE      DEST.     1    2    3    4    10    26    27
  1135.  
  1136.  
  1137.   G1         ALL     INF  INF  INF  INF    0     0    INF
  1138.   G2         G1       0    1    1    2     1     0     2
  1139.   G1         G2      INF  INF  INF  INF    0     0    INF
  1140.   G1         G3       1    2    2    3     0     0     3
  1141.   G1         G4       1    2    2    3     0     0     3
  1142.   G1         G5(10)   1    2    2    3     0     0     3
  1143.   G1         G5(26)   1    2    2    3     0     0     3
  1144.   G3         G1       1    0    1    2    INF    0     1
  1145.   G1         G2      INF   1   INF  INF    0     0     2
  1146.   G1         G3       1   INF  INF   2     0     0    INF
  1147.   G1         G4       1    1    2    2     0     0     2
  1148.   G1         G5(10)   1    1    2    2     0     0     2
  1149.   G1         G5(26)   1    1    2    2     0     0     2
  1150.   G4         G1      INF  INF   1    0     0    INF   INF
  1151.   G1         G2      INF   1   INF   1     0     0     2
  1152.   G1         G3       1   INF  INF   1     0     0    INF
  1153.   G1         G4       1    1   INF  INF    0     0     2
  1154.   G1         G5(10)   1    1    2    1     0     0     2
  1155.   G1         G5(26)   1    1    2    1     0     0     2
  1156.   G5(10)     G1       1    1    0    1     0     0     2
  1157.   G5(26)     G1       1    1    0    1     0     0     2
  1158.   G1         G2      INF   1    1    1     0     0     2
  1159.   G1         G3       1   INF   1    1     0     0    INF
  1160.   G1         G4       1    1    1   INF    0     0     2
  1161.   G1         G5(10)   1    1   INF   1     0     0     2
  1162.   G1         G5(26)   1    1   INF   1     0     0     2
  1163.            Assume loss of connectivity by G2 to Net.#1.
  1164.   G2         G1      INF   1    1   INF   INF    0     2
  1165.   G1         G2       7    1    1    1     0     0     2
  1166.   G1         G3      INF  INF   1    1     0     0    INF
  1167.   G1         G4      INF   1    1   INF    0     0     2
  1168.   G1         G5(10)  INF   1   INF   1     0     0     2
  1169.   G1         G5(26)  INF   1   INF   1     0     0     2
  1170.  
  1171.     
  1172.                               -22-
  1173.  
  1174.  
  1175.  
  1176. IEN 196                                         11 September 1981
  1177.  
  1178.  
  1179. However,  in  this  case,  G3 has two paths of distance 1 through
  1180. which it can reach Net.#10.   G3  can  go  through  G1  to  reach
  1181. Net.#10  in  1 hop or it can go through G5.  Since both paths are
  1182. equal and minimum distance, both  are  reported  in  the  routing
  1183. update.
  1184.  
  1185. When routing updates are constructed to include both distance and
  1186. connectivity  information  as  described  above, gateways receive
  1187. enough information  to  perform  path  checks.   This  capability
  1188. enables gateways to avoid shuttling problems.
  1189.  
  1190. The performance of path checks is illustrated in  Figure  7.   In
  1191. Figure  8,  step 8, G2 sends a routing update which shows that G2
  1192. has lost connectivity to Net.#1 (i.e., distance =inf.).  G1  then
  1193. recomputes  its  minimum  distance  and  routing  with respect to
  1194. Net.#1.  In these calculations G1 wants to find the shortest path
  1195. but also wants to ensure that it is a "true" path.  Therefore, G1
  1196. looks at the first path of distance 1.  This path is provided  by
  1197. G3.   However,  G3's  "next" neighbor address on this path is G2.
  1198. G2 now shows a path of infinity to Net.#1, so G1 rejects  the  G3
  1199. route.  In examining the other routes of distance 1 (i.e., G5(10)
  1200. and G5(26)), G1 finds that they all go through G2 which G1  knows
  1201. is disconnected.  Thus, all the paths of distance 1 are rejected.
  1202.  
  1203. Next, G1 looks at the route of distance 2  provided  by  G4.   G4
  1204. shows  two  "next"  addresses,  G1  and  G5,  G1 rejects the path
  1205. through "next" address G1 since this path would obviously  result
  1206. in  shuttling.   G1  then traces the route through "next" address
  1207. G5.  Looking at the routing update provided by G5, G1  sees  that
  1208. G5  intends  to route traffic addressed to Net.#1 through G2.  G2
  1209. has already been identified as a dead-end.  As  G1  has  examined
  1210. all  known  routes  to  Net.#1  and found no acceptable route, G1
  1211. determines that it is infinity distance to  Net.#1  and  sends  a
  1212. routing  update to all its neighbors showing infinity distance to
  1213. Net.#1 (step 9).
  1214.  
  1215. The rules involved in the routing scheme described in the example
  1216. plus a few additional rules of the proposed  routing  scheme  are
  1217. defined as follows:
  1218.  
  1219.  A.  On transmission of routing updates, the gateway reports its
  1220.      actual   distance   (minimum  distance  vector)  from  each
  1221.      network.   In  addition,  for  each  network,  the  gateway
  1222.      reports  the  "next"  gateway address through which it will
  1223.      route any packets addressed to the network.  If  more  than
  1224.      one  path  of the same minimum distance exists, the gateway
  1225.      will  report  all   possible   "next"   gateway   addresses
  1226.      associated  with  that  network.  In IEN # 109 terminology,
  1227.      then, each gateway exchanges its "minimum distance  vector"
  1228.      and  its  "routing table (list of neighbor gateways through
  1229.      which to send traffic to each network)."
  1230.  
  1231.                               -23-
  1232.  
  1233.  
  1234.  
  1235. IEN 196                                         11 September 1981
  1236.  
  1237.  
  1238.  B.  On  transmission  of  routing  updates,  the gateway sets a
  1239.      timer The  transmitting  gateway  does  not  recompute  its
  1240.      minimum  distance  vector  or  send any new routing updates
  1241.      prior to timer expiration.
  1242.  
  1243.  C.  Gateways calculate their routing updates and routing tables
  1244.      on the basis of the minimum distance rule.  Having selected
  1245.      the  minimum distance path to a network, the gateway checks
  1246.      the "next" gateway address.
  1247.  
  1248.      1.  If  the  "next"  gateway address is this gateway this
  1249.          path  is  considered  unacceptable   and   the   next
  1250.          candidate path is checked.
  1251.  
  1252.      2.  If the "next" gateway  address  is  other  than  this
  1253.          gateway,  use  the  information in the routing update
  1254.          matrix to determine if this path (distance  of  1  or
  1255.          greater)  is  through  a  gateway  which has reported
  1256.          "infinite" distance to the network in  question.   If
  1257.          any  step  of  the  path is through a gateway showing
  1258.          "infinite" distance  to  the  network,  the  path  is
  1259.          considered  unacceptable  and the next candidate path
  1260.          is checked.
  1261.  
  1262. Figure   8   shows   the  routing  updates  transmitted  for  the
  1263. configuration shown in Figure 7 when routing is performed IAW IEN
  1264. #  109.   Figure  8 shows the routing updates transmitted for the
  1265. same configuration (Figure 7) when the proposed routing scheme is
  1266. used.  Both examples are worked from the perspective of G1.
  1267.  
  1268. The  examples  show  the  differences  in  the  routing   updates
  1269. generated  under  each  rule.   In  both  cases, packets would be
  1270. routed correctly.  In the proposed routing scheme (see Figure 8),
  1271. fewer  routing  updates  are  transmitted  with  the same results
  1272. obtained.  This reduced traffic is due,  in  part,  to  the  rule
  1273. requiring   the   gateway   to   observe   a  time-delay  between
  1274. transmission of  routing  packets.   This  rule  is  particularly
  1275. useful  when  bringing  a  gateway  on-line because it allows the
  1276. gateway to  receive  updates  from  all  or  almost  all  of  its
  1277. neighbors  before responding with its next updates.  In addition,
  1278. the gateway is able to respond to the  loss  of  connectivity  to
  1279. Net.#1 correctly based on the update input from G2 (see Figure 8)
  1280. following the new method whereas, following the  old  rules  (see
  1281. Figure  9),  G1  must  receive  updates from all neighbors before
  1282. correctly determining that it has no path to Net.#1.
  1283.  
  1284.  
  1285.                               -24-
  1286.  
  1287.  
  1288.  
  1289. IEN 196                                         11 September 1981
  1290.  
  1291.  
  1292. Under  the  proposed  method,  the  gateway  has  a  more complex
  1293. algorithm  to  calculate  its  routing  table.    However,   once
  1294. calculated,  the gateway does not need to "tailor" the updates to
  1295. each neighbor but sends the same information  to  all  neighbors.
  1296. Also,  the  gateway  does  not maintain a copy of the last update
  1297. transmitted to determine whether there is new information  to  be
  1298. transmitted  since  it  transmits  updates  only when its routing
  1299. table changes.  Under IEN #  109,  the  gateway  is  required  to
  1300. maintain  copies  of  each  update last sent to each neighbor and
  1301. compose the new "tailored" updates  on  an  individual  basis  to
  1302. those last sent.
  1303.  
  1304. Finally, the proposed routing method can be correctly implemented
  1305. without  requiring  any  special  rules  regarding  treatment  of
  1306. non-routing neighbors.   The  path  checks  built  into  the  new
  1307. routing  scheme  preclude  the shuttling problems described above
  1308. which could have occured if non-routing gateways were not treated
  1309. as exceptions.
  1310.  
  1311.  
  1312.  
  1313.  
  1314.  
  1315.  
  1316.  
  1317.  
  1318. References
  1319.  
  1320.  1)  V.   Strazisar, "Gateway Dynamic Routting", IEN # 25, Bolt,
  1321.      Beranek and Newman, January 25, 1978.
  1322.  
  1323.  2)  V.    Strazisar,   R.    Perlman,   "Gateway   Routing,  An
  1324.      Implementation Specification", IEN # 30, April 11, 1978.
  1325.  
  1326.  3)  V.   Strazisar, "How to Build a Gateway", IEN # 109, August
  1327.      31, 1979.
  1328.  
  1329.  
  1330.  
  1331.  
  1332.  
  1333.  
  1334.  
  1335.  
  1336.  
  1337.  
  1338.  
  1339.  
  1340.  
  1341.                               -25-
  1342.  
  1343.  
  1344.